Users may store documents in a remote repository (e.g., database, cloud storage, and the like) for convenience, accessibility, storage capacity, reliability, backup capabilities, security, or other reasons. Such documents may contain sensitive, private, and/or personal information that the user does not wish to divulge regarding the user's health, finances, or other sensitive data. In some situations, contractual, legal, regulatory, or other obligations may require the entity which administers the remote repository to minimize the risk of unauthorized access to a user's documents. However, if the documents are stored in an unencrypted form on the remote repository, there may be few safeguards to prevent the administering entity from accessing a user's personal documents.
A user may address this concern by encrypting the documents at a client computing device, and storing the documents in encrypted form at the remote repository. This approach prevents the administering entity (or anyone else) from examining the documents, but may also prevent the user from performing operations on the stored documents. For example, the encryption of the documents prevents the user from performing an online search of the documents. The user may address this situation by downloading all the documents back to the client computing device, decrypting them all, and performing the desired search, but this solution may be time consuming and runs counter to the user's initial motivation for storing the documents in the remote repository.
To enable searches to be performed over encrypted document stores, the cryptographic community has developed a technique that is commonly referred to as Searchable Symmetric Encryption (SSE). One such SSE technique, for example, operates by storing an encrypted index together with the encrypted documents at a remote repository. The user then generates and submits a search token which is deterministically derived from a search term, but which conceals the search term. The remote repository then uses the encrypted index to identify and return a list of document identifiers that are associated with the search term. In this approach, the remote repository does not learn the identity of the search term associated with the search token, nor does the remote repository learn the identity of the documents conveyed in the search results. However, such existing SSE techniques fail to support more complex queries, and are therefore somewhat limited in their utility.